"""
例15　飞行棋
1．问题描述
一维棋盘，起点在棋盘的最左侧，终点在棋盘的最右侧，棋盘上有
几个位置和其他位置相连，如果A与B相连，但连接是单向的，即当棋
子落在位置A时，可以选择不投骰子，直接移动棋子从A到B，但不能从
B移动到A。给定这个棋盘的长度（length）和位置的相连情况
（connections），用六面的骰子（点数1~6），问最少需要投几次才能
到达终点。
2．问题示例
输入length=10和connections=[[2，10]]，输出为1，可以0 -> 2（投骰
子），2->10（直接相连）。输入length=15和connections=[[2，8]，[6，
9]]，输出为2，因为可以0->6（投骰子），6->9（直接相连），9 -> 15（投骰子）
3．运行结果
棋盘长度：15
连接：[[2,8],[6,9]]
最小需要：2
用python实现
"""

from collections import deque


def min_dice_tosses(length, connections):
    # 将所有可直达位置加入队列，并记录到达这些位置所需的投掷次数为0
    queue = deque([(0, 0)])
    visited = {0: 0}  # 记录已访问位置及其所需投掷次数

    while queue:
        current_pos, tosses = queue.popleft()

        # 判断当前位置是否达到终点
        if current_pos == length - 1:
            return tosses

        # 遍历当前位置可以直接到达的所有位置
        for next_pos in get_reachable_positions(current_pos, connections):
            # 如果新位置未被访问过，则添加至队列，并更新其所需投掷次数
            if next_pos not in visited:
                visited[next_pos] = tosses
                queue.append((next_pos, tosses))

    raise ValueError("无法到达终点")


def get_reachable_positions(position, connections):
    # 返回从给定位置可以直接到达的新位置列表
    return [connection[1] for connection in connections if connection[0] == position]


# 示例测试
length = 15
connections = [[2, 8], [6, 9]]
print(f"棋盘长度：{length}")
print(f"连接：{connections}")
print(f"最小需要：{min_dice_tosses(length, connections)}")
